package com.liunian.algorithmstudy.backtracking.hard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class FindItinerary332 {

	/**
	 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
	 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
	 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
	 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

	 示例 1：
	 输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
	 输出：["JFK","MUC","LHR","SFO","SJC"]

	 示例 2：
	 输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
	 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
	 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
	 */
	LinkedList<String> res = new LinkedList<>();
	public List<String> findItinerary(List<List<String>> tickets) {
		Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
		res.add("JFK");
		boolean[] used = new boolean[tickets.size()];
		backTracking(tickets, used);
		return res;
	}

	private boolean backTracking(List<List<String>> tickets, boolean[] used) {
		if (res.size() == tickets.size() + 1) {
			return true;
		}
		for (int i = 0; i < tickets.size(); i++) {
			if (i > 0 && tickets.get(i).equals(tickets.get(i - 1)) && !used[i - 1]) {
				continue;
			}
			if (!used[i] && res.getLast().equals(tickets.get(i).get(0))) {
				res.add(tickets.get(i).get(1));
				used[i] = true;
				if (backTracking(tickets, used)) {
					return true;
				}
				used[i] = false;
				res.removeLast();
			}
		}
		return false;
	}

}
